/**
 * Полиморфный контейнер типа "дерево", каждый элемент которого имеет
 * неограниченное количество потомков и родителей.
 * Корнем дерева является первый элемент.
 */

#ifndef _TREE_H
#define	_TREE_H

#include <cassert>
#include <stack>
#include <list>
#include <iostream>
#include "InnerTreeIterator.h"
#include "TreeNode.h"
#include "TreeException.h"
#include "TreeIterator.h"
#include "common/TreeAllocator.h"
#include "common/NullPointerException.h"
#include "common/RuntimeException.h"
#include "TreeSerializer.h"
#include "conf.h"

namespace etu {
namespace tree {

template <typename T> class TreeIterator;
template <typename T> class InnerTreeIterator;

template <typename T>
class Tree {

public:
	typedef class common::TreeAllocator<TreeNode<T>* > Allocator;
	typedef typename std::list<TreeNode<T> *, Allocator > NodeList;
	typedef typename std::list<TreeNode<T> *, Allocator >::iterator NodeListIterator;

    typedef typename std::list<T>::const_iterator ListIterator;
private:
    TreeNode<T>* root;

public:

    /**
     * Создание пустого дерева
     */
    Tree() {
        this->root = NULL;
    }

    /**
     * Конструктор копирования.
     * Происходит операция поверхностного копирования
     */
    Tree(const Tree& orig) {
        this->root = orig.root;
    }

    /**
     * Деструктор
     */
    ~Tree() {
        this->clear();
    }

    /**
     * Создание полной копии дерева (deep copy)
     * @return копия дерева
     */
    Tree<T>* clone() const {
        Tree<T>* ret = new Tree<T>();
        ret->root = this->root->clone();
        return ret;
    }

    /**
     * Получение количества элементов в дереве
     * @return количество элементво в дереве
     */
    int getSize() const {
        #ifdef __DEBUG__
        /*
         * Преусловия: нет
         */
        #endif

        int ret = 0;

        if(!this->isEmpty()) {
            InnerTreeIterator<T> it(* this);
            TreeNode<T>* node = it.next();

            while(node != NULL) {
                ret++;
                node = it.next();
            }
        }

        return ret;
    }

    /**
     * Задание корня дерева.
     * Если ранее он уже был задано, то старое значение будет удалено.
     * @param value значение нового корня дерева
     */
    void setRoot(const T& value) {
        #ifdef __DEBUG__
        /* Предусловия: нет
         */
        #endif

        if(this->root != NULL) {
            this->clear();
        }

        this->root = TreeNode<T>::newRootNode(value);

        #ifdef __DEBUG__
        this->checkInvariants();

        /*
         * Постуловия:
         * 1) Дерево должно содержать ровно один элемент
         * 2) Дерево должно содержать корневой элемент, 
         * значение которого совпадает с заданным
         */

        assert(this->getSize() == 1);
        assert(this->root != NULL);
        assert(this->root->getValue() == value);
        assert(this->getRoot() == value);
        #endif
    }

    /**
     * Получение корня дерева
     * @return корень дерева
     * @throws TreeException если дерево является пустым
     */
    T getRoot() const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Преусловия:
         * 1) Дерево не пустое, то есть содержит корневое значение
         */
        #endif

        if(this->isEmpty()) {
            throw TreeException("Tree is empty");
        }

        return this->root->getValue();
    }

    /**
     * Проверка, является ли дерево пустым
     * @return true, если дерево является пустым; иначе false
     */
    bool isEmpty() const {
        #ifdef __DEBUG__
        /*
         * Преусловия: нет
         */
        #endif

        return (this->root == NULL);
    }

    /**
     * Проверка, является ли одно значением потомком другого в данном дереве
     * @param child значение узла-потомка
     * @param parent значение узла-родителя
     * @throws TreeException если дерево не содержит узла-родителя
     */
    bool isChild(const T& child, const T& parent) const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Преусловия:
         * 1) Дерево должно содержать узел-родитель с заданным значением
         */
        #endif

        TreeNode<T>* parentNode = this->findNode(parent);

        if(parentNode == NULL) {
            throw TreeException("Дерево не содержит данные о родителе");
        }
        
        return parentNode->hasChild(child);
    }

    /**
     * Проверка, содержится ли элемент в дереве или нет
     * @param value true, если дерево содержит элемент; иначе false
     */
    bool contains(const T& value) const {
        #ifdef __DEBUG__
        /*
         * Предусловия: нет
         */
        #endif

        bool ret = false;

        if(!this->isEmpty()) {
            TreeNode<T>* node = this->findNode(value);
            ret = (node != NULL);
        }

        return ret;
    }

    /**
     * Получение элементов-родителей для заданного элемента
     * @param value элемент, для которого нужно получить список элементов-родителей
     * @return список значений, являющихся узлами-родителями для заданного элемента
     * @throws TreeException если элемент не содержится в дереве
     */
    std::list<T>* getParents(const T& value) const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Предусловия:
         * 1) Дерево должено содержать узел с заданным значением
         */
        #endif

        TreeNode<T>* node = this->findNode(value);

        if(node == NULL) {
            throw TreeException("Дерево не содержит данные о потомке");
        }

        return node->getParentValues();
    }

    /**
     * Проверка, имеет ли элемент потомков в дереве или нет
     * @param value элемент, для которого требуется найти потомков
     * @return true, если элемент не содержит в дереве потомков; иначе false
     * @throws TreeException если элемент не содержится в дереве
     */
    bool hasChilds(const T& value) const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Предусловия:
         * 1) Дерево должно содержать узел с заданным значением
         */
        #endif

        int ret = 0;
        TreeNode<T>* node = this->findNode(value);

        if(node != NULL) {
            ret = node->getChildsCount();
        }

        return ret;
    }

    /**
     * Проверка, имеет ли элемент узлов-родителей в дереве или нет
     * @param value элемент, для которого требуется найти узлы-родители
     * @return true, если элемент не содержит в дереве узлов-родителей; иначе false
     * @throws TreeException если элемент не содержится в дереве
     */
    bool hasParents(const T& value) const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Предусловия:
         * 1) Дерево должно содержать узел с заданным значением
         */
        #endif

        int ret = 0;
        TreeNode<T>* node = this->findNode(value);

        if(node != NULL) {
            ret = node->getParentsCount();
        }

        return ret;
    }

    /**
     * Получение потомков для заданного элемента
     * @param value элемент, для которого нужно получить список потомков
     * @return список значений, являющихся потомками для заданного элемента
     * @throws TreeException если элемент не содержится в дереве
     */
    std::list<T>* getChilds(const T& value) const throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Предусловия:
         * 1) Дерево должно содержать узел с заданным значением
         * 
         */
        #endif

        TreeNode<T>* node = this->findNode(value);

        if(node == NULL) {
            throw TreeException("Дерево не содержит данные о родителе");
        }

        return node->getChildValues();
    }

    void addAllParents(Tree<T>* tree, const T current)
    {
      std::list<T>* parents = this->getParents(current);

      for(ListIterator it = parents->begin(); it != parents->end(); it++)
      {
    	  tree->addParent(current, *it);
    	  addAllParents(tree,*it);
      }
    }

    void addAllChilds(Tree<T>* tree, const T current)
    {
      std::list<T>* childs = this->getChilds(current);

      for (ListIterator it = childs->begin(); it != childs->end(); ++it)
      {
    	  tree->addChild(current, *it);
    	  addAllChilds(tree,*it);
      }
    }

    Tree<T>* getSibs(const T value) throw(TreeException) {
        #ifdef __DEBUG__
        /*
         * Предусловия:
         * 1) Дерево должно содержать узел с заданным значением
         *
         */
        #endif

     	Tree<T>* ret = new Tree<T>();
    	ret->setRoot(value);
    	addAllParents(ret,value);
    	addAllChilds(ret,value);

    	return ret;
    }

    /**
     * Получение итератора для данного дерева
     * @return итератор для дерева
     */
    TreeIterator<T>* getIterator() const {
        #ifdef __DEBUG__
        /*
         * Предусловия: нет
         */
        #endif

        return new TreeIterator<T>(* this);
    }

    /**
     * Добавление потомка для заданного элемента в дереве.
     * Если элемент уже содержит такого потомка, то операция будет проигнорирована.
     * @param parent элемент, к которому будет добавлен потомок.
     * @param child новый потомок заданного элемента
     * @return false, если элемент дерева содержит данного потомка; иначе true
     * @throws TreeException если элемент не содержится в дереве
     */
    bool addChild(const T& parent, const T& child) throw(TreeException) {
        #ifdef __DEBUG__
        /* Предусловия:
         * 1) Дерево должно содержать узел с заданным значением узла-родителя
         */
        #endif

        TreeNode<T>* parentNode = this->findNode(parent);

        if(parentNode == NULL) {
            throw TreeException("Дерево не содержит данные о родителе");
        }

        if(parentNode->hasChild(child)) {
           return false;
        }

        TreeNode<T>* childNode = this->findNode(child);

        if(childNode != NULL) {
            parentNode->addChild(childNode);
            return true;
        }

        #ifdef __DEBUG__
        int oldSize = this->getSize();
        #endif

        bool ret = parentNode->addChild(child);

        #ifdef __DEBUG__
        this->checkInvariants();

        /*
         * Постуловия:
         * 1) Количество узлов в дереве стало на единицу больше,
         * если дерево не содержало узел с заданным значением потомка
         */

        if(ret) { // добавлен новый узел
            assert(oldSize + 1 == this->getSize());
        }
        #endif

        return ret;
    }

    /**
     * Добавление родителя для заданного элемента в дереве.
     * Если элемент уже содержит такого родителя, то операция будет проигнорирована.
     * @param child элемент, к которому будет добавлен родитель
     * @param parent новый родитель для заданного элемента
     * @return false, если элемент дерева содержит данного родителя; иначе true
     * @throws TreeException если элемент не содержится в дереве
     */
    bool addParent(const T& child, const T& parent) throw(TreeException) {
        #ifdef __DEBUG__
        /* Предусловия:
         * 1) Дерево должно содержать узел с заданным значением узла-потомка
         */
        #endif

        TreeNode<T>* childNode = this->findNode(child);

        if(childNode == NULL) {
            throw TreeException("Дерево не содержит данные о потомке");
        }

        if(childNode->hasParent(parent)) {
            return false;
        }

        TreeNode<T>* parentNode = this->findNode(parent);

        if(parentNode != NULL) {
            childNode->addParent(parentNode);
            return true;
        }

        #ifdef __DEBUG__
        int oldSize = this->getSize();
        #endif

        bool ret = childNode->addParent(parent);

        #ifdef __DEBUG__
        this->checkInvariants();

        /*
         * Постуловия:
         * 1) Количество узлов в дереве стало на единицу больше,
         * если дерево не содержало узел с заданным значением родителя
         */

        if(ret) { // добавлен новый узел
            assert(oldSize + 1 == this->getSize());
        }
        #endif
        
        return ret;
    }

    /**
     * Удаление элемента из дерева
     * @param удаляемый элемент
     * @throws TreeException если элемент не содержится в дереве
     */
    void remove(const T& value) throw(TreeException) {
        #ifdef __DEBUG__
        /* Предусловия:
         * 1) Удаляемое значение содержится в дереве
         */
        #endif

        TreeNode<T>* node = this->findNode(value);

        if(node == NULL) {
            throw TreeException("Дерево не содержит заданный элемент");
        }

        #ifdef __DEBUG__
        int oldSize = this->getSize();
        #endif

        if(this->root == node) {
            this->clear();
            this->root = NULL;
        } else {
            this->purgeNode(node);
        }

        #ifdef __DEBUG__
        this->checkInvariants();

        /*
         * Постуловия:
         * 1) Количество узлов в дереве стало меньше
         */

        assert(oldSize > this->getSize());
        #endif
    }

    void copyFrom(const Tree<T>& tree) {
        delete this->root;
        this->root = tree.root->clone(NULL);
    }

    friend std::ostream& operator<<(std::ostream& os, const Tree<T>& tree) {
        TreeSerializer<T> serializer;
        Tree<T>* _tree = (Tree<T> *) &tree;

        os << serializer.serialize(_tree);

        return os;
    }

    friend std::istream& operator>>(std::istream& is, Tree<T>& tree) {
        std::string src;

        std::getline(is, src);

        TreeSerializer<T> serializer;
        Tree<T>* _tree = serializer.deserialize(src);
        tree.copyFrom(* _tree);

        delete _tree;

        return is;
    }

    void clear() {
        if(this->root != NULL) {
            std::stack<TreeNode<T>* > nodes;

            InnerTreeIterator<T> it(* this);

            TreeNode<T>* node = it.next();
            nodes.push(node);

            while(node != NULL) {
                node = it.next();
                nodes.push(node);
            }

            while(!nodes.empty()) {
                delete nodes.top();
                nodes.pop();
            }
        }
    }

private:

    void purgeNode(TreeNode<T>* node) {
        this->clearNodeChilds(node);
        this->clearNodeParents(node);

        delete node;
    }

    /**
     * Очистка списка узлов-потомков. Используется при удалении узла
     */
    void clearNodeChilds(TreeNode<T>* parent) {
        NodeList* childs = parent->getChilds();
        NodeListIterator it = childs->begin();

        while(it != childs->end()) {
            TreeNode<T>* child = (* it);
            childs->erase(it);

            child->removeParent(parent);

            if(!this->contains(child->getValue())) {
                this->purgeNode(child);
            }

            it = childs->begin();
        }

        delete childs;
    }

    /**
     * Очистка списка узлов-родителей. Используется при удалении узла
     */
    void clearNodeParents(TreeNode<T>* child) {
        NodeList* parents = child->getParents();
        NodeListIterator it = parents->begin();

        while(it != parents->end()) {
            TreeNode<T>* parent = (* it);
            parents->erase(it);

            parent->removeChild(child);

            if(!this->contains(parent->getValue())) {
                this->purgeNode(parent);
            }

            it = parents->begin();
        }

        delete parents;
    }

    #ifdef __DEBUG__
    void checkInvariants() {
        /* Размер дерева не может быть отрицательным числом */
        assert(this->getSize() >= 0);

        if(this->isEmpty()) {
            /* Если дерево пустое, то его размер равен нулю, а указатель на
             * его корень не задан */
            assert(this->getSize() == 0);
            assert(this->root == NULL);
        } else {
            /* Если дерево не пустое, то:
             * 1) его размер является положительным числом
             * 2) задан указатель на его корень
             * 3) значение первого элемента итератора является значением корня
             * 4) получаемое значение функции получаения корня совпадает
             * со значением, хранящимся в указателе на корневой элемент
             * 5) если в дереве больше одного элемента, то корневой узел
             * должен содержать хотя бы одного потомка или родителя */
            assert(this->getSize() > 0);
            assert(this->root != NULL);
            assert(this->root->getValue() == this->getRoot());
            assert(this->getIterator()->next() == this->root->getValue());

            if(this->getSize() > 1) {
                NodeList* childs = root->getChilds();
                NodeList* parents = this->root->getParents();
                
                bool sizeInvariant = (this->root != NULL 
                    && (childs->size() > 0 || parents->size() > 0));

                delete childs;
                delete parents;

                assert(sizeInvariant);
            }
        }
    }
    #endif

    /**
     * Используется для предоставления доступа итератору к корневому узлу
     */
    friend TreeNode<T>* InnerTreeIterator<T>::getTreeRoot(const Tree<T>& tree) const;

    /**
     * Поиск узла в дереве по значению, которое содержится в нём
     * @param заданной значение, узел для которого нужно найти
     * @return узел, содержащий данное значение;
     * NULL, если узлов, содержащий заданное значение, нет
     */
    TreeNode<T>* findNode(const T& value) const {
        TreeNode<T>* ret = NULL;
        InnerTreeIterator<T> it(* this);
        TreeNode<T>* node = it.next();

        while(node != NULL) {
            if(node->getValue() == value) {
                ret = node;
                break;
            }

            node = it.next();
        }

        return ret;
    }
};

}
}

#endif	/* _TREE_H */

